package leetcode.code0327;

public class Solution1 extends Solution327 {

	long[] sums;
	int lower, upper;

	@Override
	public int countRangeSum(int[] nums, int lower, int upper) {
		this.lower = lower;
		this.upper = upper;
		int len = nums.length;
		sums = new long[len];
		sums[0] = nums[0];
		for (int i = 1; i < nums.length; i++) {
			sums[i] = sums[i - 1] + nums[i];
		}
		return process(0, len - 1);
	}

	public int process(int L, int R) {
		if (L == R) {
			return sums[L] >= lower && sums[L] <= upper ? 1 : 0;
		}
		int M = L + ((R - L) >> 1);
		return process(L, M) + process(M + 1, R) + merge(L, M, R);
	}

	public int merge(int L, int M, int R) {
		int ans = 0;
		int l = L, r = L;
		for (int i = M + 1; i <= R; i++) {
			long sum = sums[i];
			long min = sum - upper, max = sum - lower;
//			[l,r)
			while (r <= M && sums[r] <= max) {
				r++;
			}
			while (l <= M && sums[l] < min) {
				l++;
			}
			ans += r - l;
		}
		long[] help = new long[R - L + 1];
		int p = 0;
		int p1 = L, p2 = M + 1;
		while (p1 <= M && p2 <= R) {
			help[p++] = sums[p1] <= sums[p2] ? sums[p1++] : sums[p2++];
		}
		while (p1 <= M) {
			help[p++] = sums[p1++];
		}
		while (p2 <= R) {
			help[p++] = sums[p2++];
		}
		for (p = 0; p < help.length; p++) {
			sums[L + p] = help[p];
		}
		return ans;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
